Cotterill begon bij Bristol City waarmee hij vanaf 2004 in de League One speelde. Met Wigan Athletic speelde hij vanaf 2006 in de Premier League maar was geen vaste waarde en werd verhuurd aan Sheffield United dat uitkwam in de Championship. Die club nam hem over en in 2009 kwam hij op een zelfde manier bij Swansea City. Met Swansea promoveerde hij in 2012 naar de Premier League. Zelf bleef Cotterill in de Championship spelen. In 2013 won hij met Doncaster Rovers de League One en sinds 2014 komt hij uit voor Birmingham City. Na een verhuur aan Bristol City verliet hij Birmingham City eind 2017. In januari 2018 ging hij in India voor ATK spelen.